import collections


# O(n^2)
# class Solution(object):
#     def findRedundantDirectedConnection(self, edges):
#         t_node = set()
#         for u, v in edges:
#             t_node.add(u)
#             t_node.add(v)
#         n = len(edges)
#         for i in range(n - 1, -1, -1):
#             d_edges = collections.defaultdict(set)
#             du = {node: 0 for node in t_node}
#             for j in range(n):
#                 if j != i:
#                     d_edges[edges[j][0]].add(edges[j][1])
#                     du[edges[j][1]] += 1
#             start = set()
#             for key in du:
#                 if du[key] == 0:
#                     start.add(key)
#             if len(start) == 1:
#                 while start:
#                     next_set = set()
#                     for u in start:
#                         for v in d_edges[u]:
#                             du[v] -= 1
#                             if du[v] == 0:
#                                 next_set.add(v)
#                     start = next_set
#                 flag = True
#                 for key in du:
#                     if du[key] != 0:
#                         flag = False
#                         break
#                 if flag:
#                     return edges[i]

# O(n)
class Solution(object):
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        p = [i for i in range(n + 1)]
        parents = [i for i in range(n + 1)]
        def find(x):
            if p[x] == x:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        self.c = None
        self.d = None

        def union(x, y):
            px = find(x)
            py = find(y)
            if px == py:
                self.c = [x, y]
            else:
                p[py] = px

        for u, v in edges:
            if parents[v] == v:
                parents[v] = u
                union(u, v)
            else:
                self.d = [u, v]

        if self.d:
            if self.c:
                return [parents[self.d[1]], self.d[1]]
            else:
                return self.d
        else:
            return self.c